1. Field of the Invention
The invention relates generally to the field of digital data processing systems.
2. Description of the Prior Art
A typical digital data processing system includes three basic elements, namely a processor element, a memory element, and an input/output element. The memory element stores information in addressable storage locations. This information includes both data and instructions for processing the data. The processor element includes one or more digital data processing units, or "processors", each of which causes information to be transferred, or fetched, to it from the memory element, interprets the incoming information as either instructions or data, and processes the data in accordance with the instructions. The results are then stored in addressed locations in the memory element.
The input/output element also communicates with the memory element in order to transfer information into the system and to obtain the processed data from it. Units comprising the input/output element normally operate in accordance with control information supplied to it by the processor element. The control information defines the operation to be performed by the input/output unit. At least one class of operations performed by an input/output unit is the transfer of user information, that is, information used by a user program, between the input/output unit and the memory element. Typical units comprising the input/output element include, for example, printers, teletypewriters, and video display terminals, and may also include secondary information storage devices such as disk or tape storage units.
In addition to functioning as input/output devices, disk storage units and, sometimes, tape storage units may also function as part of the memory element. In particular, a memory element typically includes a main memory, whose contents are accessible to the processor relatively quickly but which is generally relatively high-cost storage. Modern main memories are typically implemented using MOS or bipolar semiconductor technology and may provide on the order of a fraction of a megabyte to several tens of megabytes of storage.
In many digital data processing systems, the processor (assuming only one processor), mass storage devices and other input/output devices all communicate with a single main memory or only a few main memory modules. This may produce contention for the main memory which can interfere with the processor's ability to quickly obtain information from the main memory. This, in turn, can slow the processor's ability to execute programs. The contention problem is exacerbated if all of the units are connected to a single input/output bus, as all information that is transferred must be transferred over the single bus.
Accordingly, in many modern computer systems, the processor includes a cache memory, which is a small private memory accessible only to the processor which stores information from the most recently-requested locations in main memory and from nearby locations. In typical data processing systems, when the processor requests an item of information from a location in the main memory, it will oftentimes require the contents of adjacent locations shortly thereafter. Accordingly, when the processor is able to request information from the main memory, it requests more than it needs at that immediate time, with the expectation that it will likely need at least some of the remaining information shortly thereafter. When the processor gets the item information it then needs, it can immediately begin using it, and if it turns out that the processor can use the other information that was received, it will have that information stored in the cache, and will not have to wait until it is obtained from the main memory.
Typically a cache memory is organized into blocks each capable of storing a predetermined amount of information. When information has been retrieved from main memory and loaded into a cache block, that block is assigned an address, termed a "tag". The tag corresponds to the address of the corresponding locations in main memory from which the information was retrieved; thus the blocks of the cache are identified with the locations in the main memory. When the processor requires information, the lags in the cache can be examined to determine whether a block contains the requested information. If one does, the information is obtained from the cache; otherwise, the processor retrieves the information from the main memory.
A number of problems arise if the data processing system is a multiprocessing system, that is, if it has a number of processors each of which has access to the memory and each of which has a cache memory. For example, under some circumstances, it will be necessary to indicate to other processors that one processor has updated a location in memory which has been cached. Otherwise, the processors which may have cached the updated data may operate on stale data from their caches.
In addition, under some circumstances data retrieved by a processor should not be cached. For example, if the processor is performing a read-modify-write operation, it will read the contents of a location, modify it and write the modified data to the same location. Usually, data retrieved during a read-modify-write operation will not be cached. Similarly, data retrieved from input/output units should not be cached. Since processors normally cache retrieved data, it will be desirable to indicate to a retrieving processor when the data should not be cached.